package 动态规划.打家劫舍;

public class 打家劫舍lc198 {

	
	public static void main(String []args) {
//		int nums[] = {1,2,3,1};
		int nums[] = {2,7,9,3,1};
		System.out.println(solution(nums));
		System.out.println(dp(nums));
	}
	
	public static int solution(int choice[]) {
		int len = choice.length;
		if(len == 0)
			return 0;
		if(len == 1)
			return choice[0];
	return	process(choice,0,len);
	}
	
	public static  int process(int choice[],int index,int len) {
		if(index >= len)
			return 0;
		int ans1 = 0;
		// 偷窃  当前  门户
		ans1 = process(choice,index + 2,len) + choice[index];
		
		int ans2 = 0;
		ans2 = process(choice,index + 1,len);
		return Math.max(ans1, ans2);
	}
	
	// dp 解法
	public static int dp(int choice[]) {
		int N = choice.length;
		int dp[] = new int [N + 2];
		for(int i = N - 1; i >= 0;i-- ) {
			dp[i] = Math.max(dp[i + 2] + choice[i], dp[i + 1]);
		}
		return dp[0];
	}
	// 主要是在 一些 basecase 上面进行了小小的改动！
	public int dpNew(int[] nums){
		int len = nums.length;
		int[] dp = new int [len + 1];
		dp[len - 1] = nums[len - 1];
		for(int i = len -2 ;i >= 0;i--){
			dp[i] = Math.max(dp[i + 1],dp[i + 2] + nums[i]);
		}
		return dp[0];
	}
	// 然后 进行一个小小的  内存的 优化！
	// 注意这个优化的方式是什么
	// 还有点 小 难搞 ， 有点小饶
	// 下面是错误的  代码！
	public int dpMemory(int[] nums){
		int len = 0;
		int mem1 = nums[len - 1], mem2 = 0;
		int cur = 0;

		for(int i = len - 2;i >= 0;i--){
			cur = Math.max(mem2 + nums[i], mem1);
			mem2 = mem1;
			mem2 = cur;
		}
		return cur;
	}

	// 得到了 一些小小的灵感！
	public int dpFinal(int[] nums){
		int len = nums.length;
		// 现在 可以省略了
//		if(len == 1){
//			return nums[0];
//		}
		int[] dp = new int[3];
//		 一开始就 像下面 这样 把 dp[0]初始化， 就不需要上面的判断这个len == 1,
		dp[0] = dp[1] = nums[len - 1];
		for(int i = len - 2;i >= 0;i--){
			 dp[0] = Math.max(dp[1],dp[2] + nums[i]);
			 dp[2] = dp[1];
			 dp[1] = dp[0];
		}
		return dp[0];
	}


}
